"""
最大路径和(基础版)

从下图三角形的顶端出发，不断移动到在下一行与其相邻的元素(例如数字7只能移动到下一行的2或者4，而不能到达6)，
得到的最大路径和(红色数字表示的路径)是23。
            3
           7 4
          2 4 6
         8 5 9 3

如上图，最大路径和为 3 + 7 + 4 + 9 = 23。求从下面的三角形顶端出发到达底部，所能够得到的最大路径和。
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

【注：在上面这个问题中，由于只有16384条路径，通过尝试所有的路径来解决问题是可行的。
但是如果三角形变大，暴力破解将不能解决，而需要一个更加聪明的办法】
"""
s='''75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23'''
print('dasd')

    


#动态规划的思想解决
#可参见：http://www.jianshu.com/p/558294dae12e
# import copy#引入复制的包
# #读取数据
# fan=open(r'C:\Users\GWT9\Desktop\secries.txt')
# an=[]#存储数据
# weizhi=[]#存储位置，用于记录经过的数字的坐标
# for i in range(15):
#     an.append([])
#     weizhi.append([])
#     x=fan.readline()
#     for j in range(15):
#         try:
#             an[i].append(int(x[j*3:(j*3)+2]))
#             weizhi[i].append([[i,j]])
#         except ValueError:
#             pass
# fan.close()
# copyan=copy.deepcopy(an)#深度复制，记录经过的数字需要用到
# #根据值得大小取坐标的函数
# def GetCoordinate(shuzu,hang,lie):
#     if shuzu[hang][lie]>shuzu[hang][lie+1]:
#         return [hang,lie]
#     else:
#         return [hang,lie+1]
# #开始计算
# for ii in range(len(an)-2,-1,-1):
#     for j in range(len(an[ii])):
#         ff=GetCoordinate(an,ii+1,j)
#         weizhi[ii][j]+=[weizhi[ff[0]][ff[1]]][0]#添加数字比较大的坐标  
#         an[ii][j]=max(an[ii+1][j],an[ii+1][j+1])+an[ii][j]#选择数字和比较大的路径

# record=[]#根据记录的坐标，选择数字
# for ii in weizhi[0][0]:
#     record.append(copyan[ii[0]][ii[1]])
# print(record)#经过的数字列表，从顶端开始
# #[75, 64, 82, 87, 82, 75, 73, 28, 83, 32, 91, 78, 58, 73, 93]
# #最大的路径和
# print(an[0][0])
# 答案：1074